import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class Cardinalitysorting {
    public static void main(String[] args) {
        int[] arr=new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i]=(int) (Math.random()*80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSSS");
        String s1 = simpleDateFormat.format(date1);
        System.out.println("排序前：" + s1);
        Cardinality(arr);
        Date date2 = new Date();
        String s2 = simpleDateFormat.format(date2);
        System.out.println("排序后：" + s2);
    }
    public static void Cardinality(int[] arr){
        int max=arr[0];
        for (int i1 = 1; i1 < arr.length; i1++) {
            if (arr[i1]>max){
                max=arr[i1];
            }
        }
        int maxsize=(max+"").length();
        int[][] Bucket=new int[10][arr.length];
        int[] Bucketarr=new int[10];
        for (int i = 0,n=1; i < maxsize; i++,n*=10) {
            for (int j = 0; j <arr.length ; j++) {
            int index=arr[j]/n%10;
            Bucket[index][Bucketarr[index]]=arr[j];
            Bucketarr[index]++;
            }
        int digitOfElement=0;
        for (int i2 = 0; i2 < Bucket.length; i2++) {
            if (Bucketarr[i2]!=0){
                for (int j = 0; j < Bucketarr[i2]; j++) {
                    arr[digitOfElement]=Bucket[i2][j];
                    digitOfElement++;
                }
                Bucketarr[i2]=0;
            }
        }
    }}
}
